1. Field of the Invention
The invention relates generally to processes used in digital halftoning systems to support multi-level halftoning. More particularly, the invention relates to improved processes for quantizing a set of mean-preserving Tone Transfer Functions (TTFs) for a multi-level halftoning system which minimize or at least significantly reduce the overall quantization error in the system.
Further aspects of the invention are directed to methods for determining threshold levels for assignment to threshold matrices and/or methods for specifying look-up tables, either of which (the matrices and look-up tables) may be used for converting input continuous tone representative intensity values into a predetermined number of available micro output levels for a multilevel halftone system having a predetermined halftone cell size.
2. Description of the Related Art
Processes for specifying mean-preserving TTFs for a multi-level halftoning system are described and claimed in copending U.S. patent application Ser. No. 07/918,291, entitled "A Process For Specifying Mean-Preserving Multi-Level Halftone Matrices With Varying Amounts of Modulation", filed on Jul. 22, 1992, now U.S. Pat. No. 5,444,551, issued Aug. 22, 1995 to Miller et al. The aforementioned copending application has been assigned to the present assignee hereof and is hereby incorporated by reference.
The present invention is directed to improvements over the teachings in the incorporated copending patent application (referred to hereinafter as the "Incorporated Application"), which will be better appreciated by first setting forth an overview of state of the art of digital halftoning techniques.
Generally, digital halftoning is accomplished by either bi-tonal or multi-tonal halftoning methods. Bi-tonal halftoning is widely used in the art and is a basic digital halftoning from which multi-toning halftoning methods are derived. Therefore, bi-tonal digital halftoning is discussed below as a precursor to a discussion of multi-tonal halftoning.
In general, bi-tonal halftoning converts a continuous tone image (sometimes referred to hereinafter as a "contone" image) into a halftone image consisting of a pattern of equal intensity dots. Each dot within the halftone image either exists (black) or does not exists (white), i.e., is a bi-tonal image.
More specifically, in one version of halftoning, bi-tonal digital halftoning converts a plurality of digitized intensity values representing a contone image into a plurality of halftone cells, where each halftone cell corresponds to each intensity value.
Moreover, the number of dots within each halftone cell is proportional to the magnitude of each corresponding intensity value. The intensity values are typically generated by periodically sampling a contone image using and optical scanner. Each intensity value represents the image intensity in an immediate area surrounding the location within the contone image from which the intensity value sample was taken.
Typically, each intensity value is quantized into a plurality of levels known as gray scale levels. Quantization permits each intensity value to be represented by a digital value and be processed by digital circuitry into a halftone image. For instance, if the intensity value is quantized into 256 levels, i.e., a 256 level gray scale, the intensity value can be represented by an eight bit digital word.
During bi-tonal halftoning, each intensity value is spatially mapped into a corresponding halftone cell. As noted above, each halftone cell typically encompasses a plurality of pixels, each having a bi-tonal value, i.e., either black or white. However, some applications require the number of intensity values to equal the number of pixels in the halftone cell, i.e., equal scanner and halftone resolutions. Generally speaking, regardless of the application, the arrangement of pixels in the halftone image is perceived by a viewer of the halftone image to have a gray scale intensity commensurate with the magnitude of each associated intensity value. The above described mapping process is generally known as spatial modulation.
In one prior art embodiment, a bi-tonal halftoning system operates by comparing each intensity value sample to a matrix of threshold levels and generates a halftone cell corresponding to each intensity value. Typically, this matrix has a number of elements equivalent to the number of pixels in the halftone cell. To generate the bi-tonal halftone cell, a given intensity value is compared to each threshold level in the matrix. Each pixel in the halftone cell, that corresponds to a threshold level in the threshold matrix and is lesser in value than the intensity value, could be made black; in which case each pixel in the halftone cell, that corresponds to a threshold level in the threshold matrix and is greater or equal in value when compared with the intensity value would be made white.
Thus the intensity value is mapped into an area comprised of an arrangement of black and white pixels whose overall intensity is commensurate with the magnitude of the intensity value.
The arrangement of threshold levels within the threshold matrix is generally known as dithering, more specifically, in two common forms: clustered dot dithering and dispersed dot dithering. In essence, through dithering, the threshold levels are arranged to ensure that the resultant halftone pixels that will be generated for a given cell will accurately reflect the intensity of the input intensity value associated with that cell. For a detailed discussion of dithering in bi-tonal systems, see Ulichney, Digital Halftoning, pp. 71-171 (MIT Press, copyright 1987).
The matrix comparison process, as described above, is repeated for each intensity value sampled from the original contone image. As a result, the entire image is spatially modulated into a halftone image comprised of a tile like arrangement of halftone cells each representing a different corresponding intensity value sample.
As is well known in the art, the halftoning process thus far described is useful in halftoning color images by repeating the bi-tonal process for each primary color, i.e., red, blue and green or cyan, magenta and yellow, and, subsequently overlaying the resulting color images with proper registration.
Multi-level halftoning is an extension of bi-tonal halftoning. As its name implies, multi-level halftoning replaces each black or white pixel in a bi-tonal halftone cell with a pixel having a value selected from a number of values available for each pixel. In essence, multi-level halftoning redistributes the intensity of a single intensity value into a plurality of intensity values within a halftone cell. Many display devices permit multi-level pixel display; multi-level halftoning takes advantage of this capability. For example, thermal printers are capable of printing dot sizes that correspond to each pixel intensity level. Additionally, cathode ray tube (CRT) displays can display various pixel intensities by altering an electron beam strength incident upon each pixel within the CRT display.
Typically, display devices are limited as to the number of levels that they can display. In contrast, sampling devices can produce many different output levels. Therefore, multi-level halftoning is used to convert a large number of output levels from a sampling device into a lesser number of levels compatible with a display device. For instance, if a display device can accurately display five levels while a scanner can provide a 256 level intensity value, a multi-level halftoning system must distribute each single 256 level value into a halftone cell, containing a plurality of five level pixels, that, when viewed, appears as the 256 level value.
To determine the appropriate level for each pixel in a multi-level halftone cell, an input intensity value is compared to a number of threshold matrices, i.e., N-1 matrices are used to generate N levels. Generally, the comparison process is similar to that used in bi-tonal halftoning except that the comparison process is repeated N-1 times for N-1 matrices. As in bi-tonal halftoning, each matrix contains, as matrix elements, a number of different threshold levels. The number of matrix elements is equivalent to the number of pixels in the halftone cell. The output of each comparison is a digital bit, i.e., a signal having a value of either a logical "1" or logical "0". The output bit value indicates whether the intensity value is greater than the threshold level, i.e., logical "1", or less than the threshold level, i.e., logical "0". Each output bit is stored in an intermediate matrix. Thus a set of N intermediate matrices containing digital bits is generated. An encoder combines the elements of the intermediate matrices to generate the pixel values for a halftone cell.
For example, an intensity value may be quantized by an 8-bit scanner to have a value between 0 and 255. The intensity value is compared to four matrices. Each matrix contains threshold levels arranged in a 4-by-4 matrix having various threshold levels ranging from 0 to 255.
Comparing each threshold level in each matrix to the intensity value results in four intermediate matrices containing digital values. The elements of each intermediate matrix are valued at a logical "1" whenever the intensity value is larger than the corresponding threshold level; otherwise a logical "0" is used as the matrix element. In essence, the four intermediate matrices are four bi-tonal halftone cells. The elements of each intermediate matrix having the same coordinates are combined to form a 4-bit word. Each 4-bit word is then encoded to generate a halftone output value for a pixel in the multi-level halftone cell. The resulting pixel value will range from 0 to 4, i.e., one level for each threshold matrix with one level to signify the absence of a pixel.
As in the case of bi-tonal halftoning, the threshold levels are placed in a dither pattern within each threshold matrix. The dither patterns are essentially the same as those used in bi-tonal halftoning, i.e., clustered-dot dither or dispersed-dot dither.
In the past, threshold levels in each matrix of a multi-level halftoning system were generated manually. These levels could be arranged using empirical methods to achieve a desired intensity value to halftone cell conversion. The number of threshold levels that needed to be specified is (m.times.n)(N-1), where: N is the number of desired output levels, and m and n are the dimensions in matrix elements of the threshold matrices. In practice, the number of threshold levels that must be generated can be quite large. For example, a system having 12 output levels with 8-by-8 element matrices requires that 704 threshold levels must be specified and then be properly arranged in each of 11 threshold matrices.
Moreover, to accomplish each intensity value comparison, N-1 comparator circuits associated with N-1 modulation matrices were used to produce an N-level output. Thus a conventional multi-level halftone system required a dedicated number of comparators and associated matrices to generate each of the output levels. Consequently, each halftoning system needed to be designed to accommodate a specific number of output levels to drive a specific display device. Thus, a single multi-level halftone image generating system could not be readily altered to accommodate any number of output levels and was rather inflexible.
A specific need existed in the art for apparatus and related processes that generated multi-level output values for pixels in a halftone cell in a manner which readily accommodated any number of output levels. This need was met by the teachings in U.S. Pat. No. 5,291,311, assigned to the same assignee as the present invention.
U.S. Pat. No. 5,291,511 teaches apparatus which generates multi-level values without using an arrangement of comparators and threshold matrices.
Additionally, a need existed in the art for apparatus that automatically generated threshold levels for each of the threshold matrices. This need was met by the Incorporated Application which also teaches how to specify look-up tables which are useful in converting input contone representative intensity values into a predetermined number of available micro output levels for a multilevel halftone system having a predetermined cell size.
According to the teachings of the Incorporated Application, a mean-preserving constraint, which is defined in terms of the number of positions in the halftone cell, is used to generate TTFs for each position in the halftone cell. Each TTF was quantized based on the number of micro output levels (modulation levels); however each TTF was quantized independently leading to a potential summed system quantization error which could be significant.
In view of the state of the art as illustrated it is desirable to provide improved methods for quantizing a set of mean-preserving TTFs for a multi-level halftoning system which minimize or at least significantly reduce the overall quantization error in the system.
Furthermore, in view of the state of the art, it would be desirable to provide methods for determining threshold levels for assignment to threshold matrices which may be used for converting input continuous tone representative intensity values into a predetermined number of available micro output levels for a multilevel halftone system having a predetermined halftone cell size.
Still further, it would be desirable to provide methods for specifying look-up tables which may be used for converting input continuous tone representative intensity values into a predetermined number of available micro output levels for a multilevel halftone system having a predetermined halftone cell size.
Further yet, it is desirable to provide simplified improved methods for quantizing a set of mean-preserving TTFs for a multi-level halftoning system that approximate the TTFs in a near optimal way in systems not capable of supporting computationally intensive quantization processes.